package solution;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class SolutionUsedStack {
    class TreeNode {
        TreeNode left;
        TreeNode right;
        int val;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    class ListNode {
        public int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
        public ListNode(int val,ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    List<TreeNode> list = new LinkedList<>();
    public void flatten(TreeNode root) {
        //先序遍历二叉树,每个结点放入 list 链表中
        firstOrder(root);
        //遍历链表，每个节点的左子树置为空，右子树为下一个结点
        func(list);
        //遍历链表，输出
        System.out.println(list);
    }
    private void firstOrder(TreeNode root) {
        if(root == null) {
            return ;
        }
        list.add(root);
        firstOrder(root.left);
        firstOrder(root.right);
    }
    private void func(List<TreeNode> list) {
        for (int i = 0; i < list.size(); i++) {
            list.get(i).left = null;
            list.get(i).right = list.get(i+1);
        }
    }

    public void flatten2(TreeNode root) {
        resetTree(root);
        List<TreeNode> list = new LinkedList<>();
        firstOrder(root,list);
        System.out.print(list);
    }
    private void firstOrder(TreeNode root,List<TreeNode> list) {
        if(root == null) {
            return ;
        }
        list.add(root);
        firstOrder(root.left,list);
        firstOrder(root.right,list);
    }

    private void resetTree(TreeNode root) {
        TreeNode cur = root;
        TreeNode curRight = null;
        while(cur != null) {
            curRight = cur.right;
            if(cur.left != null) {
                cur.right = cur.left;
                cur.left = null;
                TreeNode curN = cur;
                while(curN.right != null) {
                    curN = curN.right;
                }
                if(curN != curRight) {
                    curN.right = curRight;
                }
            }
            cur = cur.right;
        }
    }


    //重排链表
    public void reorderList(ListNode head) {
        ListNode midNode = middleNode(head);
        ListNode curB = midNode.next;
        midNode.next = null;
        curB = reverseList(curB);
        mergeList(head,curB);
    }

    private ListNode middleNode(ListNode cur) {
        ListNode fast = cur;
        ListNode slow = fast;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    private ListNode reverseList(ListNode cur) {
        if(cur == null) {
            return null;
        }
        ListNode prev = cur;
        cur = cur.next;
        ListNode curN = null;
        prev.next = null;
        while(cur != null) {
            curN = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curN;
        }
        return prev;
    }

    private void mergeList(ListNode curA,ListNode curB) {
        ListNode tmpB = null;
        ListNode tmpA = null;
        while(curB != null) {
            tmpB = curB.next;
            tmpA = curA.next;

            curB.next = curA.next;
            curA.next = curB;

            curA = tmpA;
            curB = tmpB;
        }
    }
}
